from bisect import bisect_right
from typing import List


# class Solution:
#     def kIncreasing(self, arr: List[int], k: int) -> int:
#         n = len(arr)
#         result = 0
#         for i in range(k, n):
#             if arr[i - k] > arr[i]:
#                 result += 1
#
#         return result

class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        n = len(arr)
        ans = 0
        for i in range(k):
            f = list()
            j, length = i, 0
            while j < n:
                length += 1
                it = bisect_right(f, arr[j])
                if it == len(f):
                    f.append(arr[j])
                else:
                    f[it] = arr[j]
                j += k
            ans += length - len(f)
        return ans


if __name__ == '__main__':
    a = Solution()
    print(a.kIncreasing([12, 6, 12, 6, 14, 2, 13, 17, 3, 8, 11, 7, 4, 11, 18, 8, 8, 3], 1))
